class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:

    def createList(self, ls:list) -> ListNode:
        head = ListNode(-1)
        cur = head
        n = len(ls)
        for i in range(n):
            cur.next = ListNode(ls[i])
            cur = cur.next
        return head.next

    def printList(self, head: ListNode):
        cur = head
        res = []
        while cur:
            res.append(cur.val)
            cur = cur.next
        print(res)

    def twoSum(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(-1)
        cur = head
        carry = 0
        while l1 or l2 or carry:
            s = (l1.val if l1 else 0) + (l2.val if l2 else 0) +carry
            val = s % 10
            carry = s // 10
            cur.next = ListNode(val=val)
            cur = cur.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return head.next

    def mergeTwoSort(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(-1)
        cur = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next

    def mergeKsort(self, ls: list) -> ListNode:
        dummy = ListNode(-1)
        cur = dummy
        k = len(ls)
        while True:
            m = 10000
            idx = -1
            for i in range(k):
                if ls[i]:
                    if ls[i].val < m:
                        m = ls[i].val
                        idx = i
            if idx == -1:
                break
            else:
                cur.next = ls[idx]
                ls[idx] = ls[idx].next
                cur = cur.next
        return dummy.next

    def mergeKsort2(self, ls: list) -> ListNode:
        if ls is None:
            return None
        k = len(ls)
        for i in range(1, k):
            ls[i] = self.mergeTwoSort(ls[i - 1], ls[i])
        return ls[k-1]


    def insertSort(self, head: ListNode) -> ListNode:
        dummy = ListNode(head.val, head)
        pre, cur = dummy, head
        while cur:
            if pre.val <= cur.val:
                pre = cur
                cur = cur.next
                continue
            p = dummy
            while p.next.val <= cur.val:
                p = p.next

            t = cur.next
            cur.next = p.next
            p.next = cur
            pre.next = t
            cur = t

        return dummy.next

    def sortList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        slow, fast = head, head.next
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next

        t = slow.next
        slow.next = None
        l1, l2 = self.sortList(head), self.sortList(t)
        self.printList(l1)
        # self.printList(l2)

        dummy = ListNode()
        cur = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return dummy.next

    def reverseList(self, head: ListNode) -> ListNode:
        pre, p = None, head
        while p:
            t = p.next
            p.next = pre
            pre = p
            p = t
        return pre

    def reverseList2(self, head: ListNode, left: int, right: int) -> ListNode:
        # l1 = s.createList([1,2,3,4,5])
        # res = s.reverseList2(l1, 2, 4)
        dummy = ListNode(0, head)
        pre = dummy

        for i in range(left-1):
            pre = pre.next

        p, q = pre, pre.next
        cur = q

        for i in range(right-left+1):
            t = cur.next
            cur.next = pre
            pre = cur
            cur = t
        p.next = pre
        q.next = cur

        return dummy.next

    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if k == 0 or head is None or head.next is None:
            return head

        cur = head
        n = 0
        while cur:
            n = n+1
            cur = cur.next

        k %= n
        if k == 0:
            return head

        slow, fast = head, head
        for i in range(k):
            fast = fast.next

        while fast.next:
            slow, fast = slow.next, fast.next

        start = slow.next
        slow.next = None
        fast.next = head
        return start

    def isPalindrome(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return True

        slow, fast = head, head.next
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        
        # 翻转
        pre, cur = None, slow.next
        while cur:
            t = cur.next
            cur.next = pre
            pre = cur
            cur = t

        while pre:
            if pre.val != head.val:
                return False
            pre, head = pre.next, head.next

        return True

    def oddEvenList(self, head: ListNode) -> ListNode:
        if head is None:
            return head
        # 基数，偶数
        odd, even = head, head.next
        even_head = even
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = even_head
        return head

    def hasCycle(self, head: ListNode) -> ListNode:
        slow, fast = head, head.next
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            if slow == fast:
                return True
        return False

class myList:

    def __init__(self):
        self.dummy = ListNode()
        self.count = 0

    def get(self, index: int) -> int:
        if index < 0 or index > self.count:
            return -1
        cur = self.dummy
        for _ in range(index):
            cur = cur.next
        return cur.val

    def addAtIndex(self, index: int, val: int):
        if index > self.count:
            return
        pre = self.dummy
        for _ in range(index):
            pre = pre.next
        pre.next = ListNode(val=val, pre.next)
        self.count += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.count:
            return
        pre = self.dummy
        for _ in range(index):
            pre = pre.next
        t = pre.next
        pre.next = t.next
        t.next = None
        self.count -= 1

if __name__ == '__main__':
    s = Solution()

    # l1 = s.createList([2,4,3])
    # l2 = s.createList([5,6,4])
    # l1 = s.createList([2,2,9,9,9])
    # l2 = s.createList([1,9,9])
    # res = s.twoSum(l1, l2)
    # s.printList(res)

    # l1 = s.createList([1,2,4,5,6,7,8])
    # l2 = s.createList([1,3,4])
    # res = s.mergeTwoSort(l1, l2)
    # s.printList(res)

    # l1 = s.createList([1,2,4,5,6,7,8])
    # l2 = s.createList([1,3,4])
    # l3 = s.createList([1,2,4])
    # res = s.mergeKsort2([l1,l2,l3])
    # s.printList(res)

    # l1 = s.createList([1,3,2,4])
    # res = s.insertSort(l1)
    # s.printList(res)

    # l1 = s.createList([1,5,3,4,0])
    # res = s.sortList(l1)
    # s.printList(res)

    # l1 = s.createList([1,5,3,4,0])
    # res = s.reverseList(l1)
    # s.printList(res)

    # l1 = s.createList([1,2,3,4,5])
    # res = s.reverseList2(l1, 2, 4)
    # s.printList(res)

    # l1 = s.createList([1,2,3,4,5])
    # res = s.rotateRight(l1, 2)
    # s.printList(res)

    # l1 = s.createList([1,2,2,1])
    # res = s.isPalindrome(l1)
    # print(res)

    l1 = s.createList([1,2,3,4,5])
    res = s.oddEvenList(l1)
    s.printList(res)


